/* 
 * fibanacci.c 
 * 
 *  Created on: 2015-3-16 
 *      Author: floydz 
 */  
  
#include <stdio.h>  
  
/* 
 * 关于long long的定义: 在C语言的C99标准扩展了新的整数类型 long long，long是32位宽， 
 * 占4个字节，long long通常被定义成 64 位宽，也就可以实现了在32位机器上可以扩展8字节的数据 
 *  
 * I64d是对应的long long类型的printf打印标识符 
 */  
  
/* 
 * fibonacci_resursive 使用递归的方法实现 
 */  
long long fibonacci_recursive(int n) {  
    if (n <= 0)  
        return 0;  
    if (n == 1)  
        return 1;  
    return fibonacci_recursive(n - 2) + fibonacci_recursive(n - 1);  
}  
  
  
/* 
 * fibonacci_iteration使用迭代的方法实现 
 */  
long long fibonacci_iteration(int n) {  
    int result[2] = { 0, 1 };  
    int i = 2;  
    long long num = 0;  
    if(n < 2) {  
        return result[n];  
    }  
    long long fib_minusone = 1;  
    long long fib_minustwo = 0;  
    for(;i <=n;i++) {  
        num = fib_minusone + fib_minustwo;  
        fib_minustwo = fib_minusone;  
        fib_minusone = num;  
    }  
    return num;  
}  
  
int main() {  
    int input;  
    long long result1, result2;  
    printf("请输入数字n:\n");  
  
    fflush(stdout);//刷新标准输出  
    scanf("%d", &input);  
    printf("你输入的数字是:%d\n", input);  
    fflush(stdout);  
    result1 = fibonacci_recursive(input);  
    result2 = fibonacci_iteration(input);  
    printf("计算所得的Fibonacci_recursive(%d)值为%ld:\n", input, result1);  
    fflush(stdout);  
    printf("计算所得的Fibonacci_iteration(%d)值为%ld:\n", input, result2);  
    fflush(stdout);  
    return 1;  
}  